package review;

import java.util.ArrayList;
import java.util.List;

public class T39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        dfs(candidates, 0, target, tmp, ans);
        return ans;
    }

    void dfs(int[]candidates,int index,int target,List<Integer>tmp,List<List<Integer>> ans) {
        if (target < 0||index==candidates.length) {
            return;
        }

        if (target == 0) {
            ans.add(new ArrayList<>(tmp));
            return; //必须要返回，不然会出现重复组合（因为在下一轮递归，不选也可以得到同样的答案）
        }

        // 选了但不移动指针
        tmp.add(candidates[index]);
        dfs(candidates, index, target - candidates[index], tmp, ans);

        // 不选且移动指针
        tmp.remove(tmp.size() - 1); //回溯
        dfs(candidates, index + 1, target, tmp, ans);
    }


    void dfs_2(int[]candidates,int index,int target,List<Integer>tmp,List<List<Integer>> ans) {
        if (index==candidates.length) {
            return;
        }

        if (target == 0) {
            ans.add(new ArrayList<>(tmp));
            return; //必须要返回，不然会出现重复组合（因为在下一轮递归，不选也可以得到同样的答案）
        }

        if (target - candidates[index] >= 0) { //先判断是否符合条件再进行递归，可以优化算法的执行时间
            // 选了但不移动指针
            tmp.add(candidates[index]);
            dfs(candidates, index, target - candidates[index], tmp, ans);

            // 不选且移动指针
            tmp.remove(tmp.size() - 1);                     //前面选了，需要回溯
            dfs(candidates, index + 1, target, tmp, ans);
        }else{
            dfs(candidates, index + 1, target, tmp, ans);   //前面没选，所以不需要回溯
        }
    }
}
